package bch.maven.plugin.guava.business.jgrapht;

import cn.hutool.core.lang.Pair;
import org.jgrapht.Graph;
import org.jgrapht.graph.DefaultDirectedGraph;
import org.jgrapht.graph.DefaultEdge;
import org.jgrapht.nio.Attribute;
import org.jgrapht.nio.DefaultAttribute;
import org.jgrapht.nio.dot.DOTExporter;

import java.io.FileWriter;
import java.io.IOException;
import java.util.*;

public class PedigreeCycleVisualizer {

    public static void main(String[] args) throws IOException {
        // 1️⃣ 构建父母关系 Map<子ID, Pair<父ID, 母ID>>
        Map<Long, Pair<Long, Long>> parentMap = new HashMap<>();
        parentMap.put(1L, Pair.of(2L, 3L));
        parentMap.put(2L, Pair.of(3L, null));
        parentMap.put(3L, Pair.of(1L, null));
        parentMap.put(4L, Pair.of(5L, 6L));
        parentMap.put(5L, Pair.of(6L, 4L));
        parentMap.put(6L, Pair.of(null, null));
        parentMap.put(7L, Pair.of(8L, 9L));
        parentMap.put(8L, Pair.of(10L, null));
        parentMap.put(9L, Pair.of(7L, null));
        parentMap.put(10L, Pair.of(null, null));

        // 2️⃣ 检测环路
        List<List<Long>> cycles = findCycles(parentMap);
        System.out.println("检测到 " + cycles.size() + " 个环：");
        for (int i = 0; i < cycles.size(); i++) {
            System.out.println("环 " + (i + 1) + ": " + cycles.get(i));
        }

    }

    /**
     * DFS 检测所有环路
     */
    private static List<List<Long>> findCycles(Map<Long, Pair<Long, Long>> parentMap) {
        List<List<Long>> cycles = new ArrayList<>();
        Set<Long> globalVisited = new HashSet<>();

        for (Long node : parentMap.keySet()) {
            dfsCollectCycles(node, parentMap, new ArrayDeque<>(), cycles, globalVisited);
        }

        return cycles;
    }

    private static void dfsCollectCycles(Long node,
                                         Map<Long, Pair<Long, Long>> parentMap,
                                         Deque<Long> path,
                                         List<List<Long>> cycles,
                                         Set<Long> globalVisited) {
        if (path.contains(node)) {
            // 找到环，从第一次出现 node 的位置截取到当前
            List<Long> cycle = new ArrayList<>();
            Iterator<Long> it = path.descendingIterator();
            boolean start = false;
            while (it.hasNext()) {
                Long n = it.next();
                if (n.equals(node)) start = true;
                if (start) cycle.add(n);
            }
            cycle.add(node); // 尾节点闭环
            Collections.reverse(cycle);
            cycles.add(cycle);
            return;
        }
        if (globalVisited.contains(node)) return;

        path.push(node);

        Pair<Long, Long> parents = parentMap.get(node);
        if (parents != null) {
            if (parents.getKey() != null)
                dfsCollectCycles(parents.getKey(), parentMap, path, cycles, globalVisited);
            if (parents.getValue() != null)
                dfsCollectCycles(parents.getValue(), parentMap, path, cycles, globalVisited);
        }

        path.pop();
        globalVisited.add(node);
    }

    /**
     * 导出 Graphviz DOT 文件，可在线可视化
     */
    private static void exportGraphviz(Map<Long, Pair<Long, Long>> parentMap,
                                       List<List<Long>> cycles,
                                       String fileName) throws IOException {
        Graph<Long, DefaultEdge> graph = new DefaultDirectedGraph<>(DefaultEdge.class);

        // 添加节点和边
        for (Map.Entry<Long, Pair<Long, Long>> e : parentMap.entrySet()) {
            Long child = e.getKey();
            Pair<Long, Long> parents = e.getValue();
            graph.addVertex(child);
            if (parents.getKey() != null) {
                graph.addVertex(parents.getKey());
                graph.addEdge(parents.getKey(), child);
            }
            if (parents.getValue() != null) {
                graph.addVertex(parents.getValue());
                graph.addEdge(parents.getValue(), child);
            }
        }

        // 高亮环节点
        Set<Long> cycleNodes = new HashSet<>();
        for (List<Long> cycle : cycles) {
            cycleNodes.addAll(cycle);
        }

        DOTExporter<Long, DefaultEdge> exporter = new DOTExporter<>(Object::toString);
        exporter.setVertexAttributeProvider(v -> {
            Map<String, Attribute> map = new LinkedHashMap<>();
            if (cycleNodes.contains(v)) {
                map.put("color", DefaultAttribute.createAttribute("red"));
                map.put("style", DefaultAttribute.createAttribute("filled"));
                map.put("fillcolor", DefaultAttribute.createAttribute("lightcoral"));
            } else {
                map.put("color", DefaultAttribute.createAttribute("black"));
            }
            map.put("label", DefaultAttribute.createAttribute(v.toString()));
            return map;
        });

        try (FileWriter writer = new FileWriter(fileName)) {
            exporter.exportGraph(graph, writer);
        }

        System.out.println("✅ Graphviz 文件已导出：" + fileName);
        System.out.println("👉 打开在线可视化工具查看：https://dreampuf.github.io/GraphvizOnline/");
    }
}
